package data_structure.queue;

/**
 * @Author: lijun
 * @Date: 2018/10/29 16:21
 * 给定一个由 '1'（陆地）和 '0'（水）组成的的二维网格，计算岛屿的数量。一个岛被水包围，并且它是通过水平方向或垂直方向上相邻的陆地连接而成的。
 * 你可以假设网格的四个边均被水包围。
 *
 * 输入:
 * 11110
 * 11010
 * 11000
 * 00000
 * 输出: 1
 *
 * 输入:
 * 11000
 * 11000
 * 00100
 * 00011
 * 输出: 3
 */
public class NumIslands {

    public int numIslands(char[][] grid) {
        int islandsNum = 0;
        int yLength = grid.length;
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[i].length; j++) {
                if (grid[i][j] == '1') {
                    islandsNum++;
                }
                bfs(i, j, grid);
            }
        }
        return islandsNum;
    }

    private void bfs(int i, int j, char[][] grid) {
        if (grid[i][j] == '1') {
            grid[i][j] = '0';

            if (i > 0)
                bfs(i-1, j, grid);
            if (i < grid.length-1)
                bfs(i+1, j, grid);
            if (j > 0)
                bfs(i, j-1,grid);
            if (j < grid[0].length-1)
                bfs(i, j+1, grid);
        }
    }


    public static void main(String[] args) {
        char[][] grid = {{'1','1','1','1','0'},{'1','1','0','1','0'},{'1','1','0','0','0'},{'0','0','0','0','0'}};
        System.out.printf("" + new NumIslands().numIslands(grid));
    }
}
